Good afternoon, I would like to start by introducing myself. I am Jon Kalb and I work for Liberty Software a Macintosh-only Software Consulting firm in the bay area.
Although I have written shipping code that makes heavy used of the Standard Template Library, I don’t hold myself out as an expert. My mantra for the standard library and Modern C++ is "learn it; love it; live it." Now I’m here to share it.
My goal for this session is not to explore the library in detail or to get into advanced or even intermediate topics. My goal is to provide an introduction to experienced C++ programmers that have little or no experience with STL.
If you are an experienced STL user, that’s great because, later in this talk I will give you a chance to share some of your hard-won knowledge.
Although there is some minor updating, this is the essentially the same session that I gave last year. I would like to see hands of anyone that was in last year’s session. As you can see from the schedule, there will be follow-on Modern C++ session later this afternoon.
One thing that I did change is the name. I like the names Modern C++ and Classic C++ because I think that consistent use of templates, namespaces, exceptions, smart pointers, standard containers, and standard strings makes using of the new ISO standard C++ like using a new language.
If you attended either of my sessions last year, you know that I spent a significant amount of time in them discussing where Metrowerks had not yet implemented the standard completely and how to work around these limitations. Fortunately for all of us, I don’t need to do that this year. Metrowerks has essentially completed implemention of the standard. If you have problems now, they are yours.
STL, or the Standard Template Library, is now a part of the draft ISO/ANSI C++ Standard. Users of STL can begin to expect it to be universally available. For those of us that are not yet familiar with STL, the future is clear–professional C++ programmers will be expected to understand and maintain objects that depend on this new library.
STL code will probably look a little strange at first and learning how to use the library will require some effort. Fortunately, STL's power, ease of use, and consistency make it worthwhile.
My focus here is going to be on giving you the information you need to begin to use STL in your code. This discussion will be about practice, not theory, which is, in a way, a shame, because the thinking behind how the library is structured and used is very interesting and fun to explore. You will see that very little knowledge of templates is needed for getting started. Only when you are ready to extend the library is writing templates required.
Before we plunge into the code-level nitty-gritty, I do want to share an overview of what it is that STL is trying to accomplish. I feel that this perspective is valuable, because I know how lost I was without it.
I was first drawn to STL as a standard container library. But as I read about STL, I was impatient that STL writers tend to start off by talking about generic algorithms, function objects, and/or iterators. If STL is about building a better list class, than why start off with these side topics?
It turns out that STL is not about containers. STL is really about generic algorithms. Containers are just a necessary step to reaching generic algorithm nirvana.
As an example of a generic algorithm, consider qsort(). qsort() is an ANSI C implementation of a generic algorithm. Regardless of the contents of your array, your data is sorted.
But consider the limitation of this kind of generic algorithm.
First, every use of qsort() requires that we code a "compare" function, even if this function is trivial. Of course, if the compare is trivial, then dereferencing a function pointer is relatively expensive. Whether or not we care depends on the proportion of time spent in compares as opposed to swaps. For most uses of qsort() this may not be significant, but it points up a weakness of this approach to generic algorithms.
Next, we have no control over construction, destruction, or assignment of the array items being sorted. All swapping is done by raw memory moves.
Also, by using void pointers, we have completely sacrificed type safety.
Finally, we are restricted to working with arrays and these must exist in the standard memory model. God, and the ANSI Standard, forbid that you use an unconventionally memory model or that your data be in a list, a tree, a file, or any container other than a simple array.
These limitations can all be overcome, and have been in STL, by the use of templates.
Before looking at the STL equivalent of qsort() I want to present a quick and dirty definition.
One of the basic building blocks of STL is the iterator. For now, I want to define an iterator as anything that can take the deference operator or, to put it another way, if it can take pointer syntax, it's an iterator.
For now, when you hear iterator, think pointer.
Now let's look at STL's version of the quick sort algorithm:
Instead of passing an array’s base address and the number and size of elements in the array we pass a pair of iterators (think pointers). Due to template magic, these iterators are type safe. We need not pass in the element size because, like type safe pointers, we can safely increment and decrement as needed.
Passing two iterators is the standard way of passing a collection of items in STL. The first iterator refers to the first item in the collection, but the second iterator, despite its name, does not refer to the last. The convention is that the second iterator points one past the last item in the collection.
Using this convention, the two iterators exactly enclose all and only the elements to be considered.
This may take some getting used to at first, but, on reflection, it makes a great deal of sense. Because the iterators may be pointers into a list, we can’t rely on the standard "less than" comparison that we are used to. As we iterate over our collection, we just need to increment our "first" iterator and compare it to our "last" iterator. When the iterators are equal (which, by definition, means that they refer to the same item), then we are done.
Note that we never dereference the "last" iterator. It may be nil or any other value. It can only be used to compare with the "first" iterator. You should always assume that dereferencing it will bus error.
Returning to the STL sort declarations, we see that the first declaration does not take a comparison function. If no comparison function is passed, the STL sort implementation will simply use the "less than" operator for comparison (of the items, not the iterators). At first glance, this may seem to be of little use, but since template magic gives us type safety, the objects to be sorted can overload the "less than" operator. Without our having to code a comparison function, the objects are sorted into their "natural" order.
In our first sample program I demonstrate the efficiency that we can achieve with templates. Often new coding technologies offer us a trade-off with power of expression or ease of use on one side and performance on the other side. This program compares quick sorting an array with qsort() and the STL sort() generic algorithm.
Two years ago, I tested this on both 68K and PowerPC machines with both the HP STL and the Modina STL implementations. The STL sort was from three to twelve times faster. This year I did a quick verification test with Metrowerk’s library on a PowerPC. My G3 PowerBook is so much faster that I actually had to increase the size of the arrays by a factor of ten in order to get meaning full results. It turned out that the template version is about six times faster. Learn it; love it; live it.
Of course, I stacked the deck with this sample program. Because the objects being sorted were of a built-in type (they are longs) and because we used the form of sort() that does not use a "compare" function object we don't have any function call overhead when doing compares. This is not necessarily a rare or exceptional case. Any compare that is inline will do this, even if we used the version of sort() that takes a function object. That is part of the point. Template magic allows us to implement a generic algorithm that, in some cases, doesn't require functional call overhead, when the traditional approach would always require it.
My point is not that generic algorithms are always more efficient than specifically coded algorithms, my point is that, using templates, we can be as efficient if not more efficient than using the traditional approaches to generic algorithms and type safety and greater flexibility are both thrown in as bonuses.
Now that we have tasted generic algorithms, we have a better idea of why implementing them leads us to iterators and containers. The whole point of generic algorithms is that the work that needs to be done does not depend on the kind of data involved.
If a class of objects supports addition, then we can accumulate. If it supports addition and division by a scalar then we can average. If it supports the "less than" operator, then we can sort. It doesn't matter if the class represents ints, floats, strings, test scores, portfolios, medical records, or box scores. It also doesn't matter if the items are stored in an array, a list, a file, or on a web server.
If our generic algorithms only worked on items that are passed to them, like min and max, then we would have no need of iterators or containers.
Most generic algorithms are designed for an arbitrary number of items. This is why we have iterators. With this single object we can get the value of an item (by dereferencing) or move to the next item in the data set (by incrementing or decrementing).
If the only containers that we ever used were arrays, then we could just use pointers and forget about this iterator nonsense. The one drawback to pointers is that they don’t hide the container from the generic algorithm. Because qsort() uses pointers, it can only operate on arrays.
Imagine a linked list. A pointer to an element in the list has part of what we need in an iterator--if we dereference it we have our element. But if we increment this pointer we don't get the next item in the list, we are pointing at some arbitrary memory location.
Now imagine that we have defined a class of objects that point at items in lists. We can override the increment operator to have the object pointer walk the list. Voila! We have a list iterator.
This also explains why iterators and containers are so closely linked. The implementation of the iterator is dependent on the nature of the container class.
We are almost ready to get down and dirty with some code, but before we start looking at containers we need to be aware of some restrictions placed on the objects that will be contained.
OK, let’s look at other standard containers and their iterators. I say other standard containers because I want to emphasize that arrays are a standand container and pointers are their iterators. The standard string class is also a standard container. I will talk more about the standard string class in my next session.
The first new containers are called vectors and deques. Vector is not a terrible intuitive name (at least it wasn’t for me). The idea is that vectors grow in only one direction. A vector is like an array except that it can grow, but only at the end. A deque is like an array except that it can grow at both the beginning and the end. I have heard the word deque pronounce as "deck" and as "D-Q" by people that insist that their pronunciation is correct. The only thing I will say is that the name come from "double ended queue."
In this sample program we play with a vector and a deque.
Note that the deque constructor supports constructions from a pair of interators. This is true for all the new containers and it can be rather handy.
This code demonstrates several functions of vectors and deques:
| empty() | which works the way you would expect for all containers. |
| push_back() | which is the workhorse for adding to a vector |
| insert() | which, although I am using it here to insert at the end of the vector, can be used to insert anywhere. Inserting in the middle of a vector or deque can be done, but it is not efficient. If you need to do this often, consider using a list. |
| pop_back() | erases the last item in the vector or deque. pop_back does not return the last item. There is a very good reason for this, which becomes apparent if you try to design an exception safe pop() member. |
| array notation | both vectors and deques use array notation. This notation returns a reference so it can be used for both reading and writing, but it cannot be used to add elements to the container. |
| erase() | which can be called to erase a collection by passing two iterators. I want to erase the elements that are the third from the end to the second to the end, but since the iterator should point passed the last item to be erased, I passed d.end() - 3 and d.end() - 1 for the range. |
Note how we declare an iterator for our container. We simply restate the container declaration followed by "scope resolution operator iterator." As container declarations tend to get a bit wordy, we often use a typedef to make life easier. I have done that for the deque declaration.
Iterating over the container is just as we discussed earlier and it is identical for both the vector and the deque.
The only other things to notice are the deque constructor, we populate by iterating across the vector, and the push_front() call. Deques can grow at both ends and the efficient way to insert at the beginning of the deque is push_front(). There is also a pop_front. These call is not supported for vectors.
Vectors, deques, arrays, and standard strings are called sequence containers because they store items in the sequence in which they are added. With one exception, other STL containers store items in sorted order and are called associative containers. The last sequence container is the list.
In this example we see that using a list is similar to the other containers. The biggest differences are in the things that you already know about the differences between array-like classes and lists. Arrays have less overhead and lists are more flexible.
Here we are showing off remove(), sort(), unique(), and reverse(), which are member functions of the list class. This class also has functions to splice() lists together or merge() sorted lists.
But in going from array-like containers to lists we did have to give up some things. We can no longer use array notation or the at() function to address items by their position in the list.
The rest of the STL containers are associative. These containers keep the items they contain in sorted order. As you would expect, at construction, we either pass a function to use as a compare function or we use the default "less than" comparison.
Because these containers are always sorted, we no longer use push_back() or push_front(). We can call insert() without passing a position argument.
In this example we use two of the associative containers, the set and the multiset. The set is a simple ordered collection that differs from the multiset only in that it does not support duplicate items. Note that the burden of excluding duplicates is assumed by the container, not the caller.
Both set and multiset have lower_bound() and upper_bound() members. These members return an iterator that refers to the lowest or highest location that an item of the passed value could be placed without violating the ordering rules.
The last two containers that we are going to examine are called the map and the multimap. As you have already guessed, the difference between them is that the multimap can contain duplicate entries.
All of the containers that we have looked at so far have been designed to contain items, but the map is designed to contain pairs of times. Each pair consists of a key and a value. When a pair is added to a map the key is used to find where, in the sort order, this pair belongs.
A map is like a set in which each item in the set has a link to another item that may be of a different type.
In this example, we create a map that maps integers to their names. We create two vectors of integers and use the random_shuffle generic algorithm to shuffle their values. Next we walk the vectors and add and subtract their corresponding values. What makes it interesting is that when we print our results we use the map to replace all the integers with their names.
We can use array notation so that the expression "map sub key" returns the map value. Learn it; love it; live it.
My final code example deals with exceptions. My best words to you are proceed with caution.
As this example shows not every call will throw exceptions when you might expect. Here the vector’s at() call will throw, but the array notation fails silently. You have been warned!
I want to leave you with a few tips:
If you have large objects or objects with expensive constructors or destructors, you might consider storing by reference rather than by value. I will speak more about this in my later session.
We have looked at all of the Modern C++ container classes expect the string class and briefly discussed generic algorithms. My hope is that you have enough information to begin to use STL in your code, but the list of items that we have not discussed is longer than the items that we have.
STL is very complex and I have deliberately tried to steer us away from complicating issue. I will touch on some of these issues in my later session. About the issues that we have discussed, I am now ready to take questions.